4368. Треугольная паутина

Перед Вами бесконечная треугольная сетка. Она устроена таким образом, что если поджечь какую-нибудь вершину, то эта вершина загорается, в следующую секунду загораются все вершины, соседние непосредственно с данной, далее все вершины, соседние с уже горящими, и т.д. Считайте, что огонь никогда не тухнет.

Изначально подожжена одна вершина. Требуется найти количество горящих вершин через n секунд.

Вход. Одно число n (0 ≤ n ≤ 10⁹).

Выход. Вывести количество горящих вершин через n секунд.

Пример входа 1	Пример выхода 1
1	7
Пример входа 2	Пример выхода 2
1500	6754501

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Первый уровень (вершины, которые загораются через 1 секунду) содержит 6 вершин. Второй уровень содержит 12 вершин, третий 18 и так далее. Получается арифметическая прогрессия с разностью 6.

Чрез n секунд будет гореть res = 1 + (6 + 12 + 18 + … + (6 + 6 * (n – 1))) вершин. Используя формулу суммы арифметической прогрессии , получим что

res = 1 + = 1 + (6 + 3*(n – 1)) * n

Реализация алгоритма

Читаем значение n. Вычисляем и выводим ответ.

scanf("%lld",&n);

res = 1 + (6 + 3 * (n - 1)) * n;

printf("%lld\n",res);